// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package flate

import (
	"fmt"
	"io"
	"math"
)

const (
	NoCompression      = 0
	BestSpeed          = 1
	BestCompression    = 9
	DefaultCompression = -1

	// 哈夫曼仅禁用Lempel-Ziv匹配搜索，仅执行哈夫曼
	// 熵编码。此模式在压缩已使用LZ风格算法（例如Snappy或LZ4）压缩的
	// 数据时非常有用，该算法缺少熵编码器。当
	// 输入流中的某些字节比其他字节出现得更频繁时，可以获得压缩增益。
	// 
	// 请注意，Huffmano只生成符合RFC 1951的压缩输出。也就是说，任何有效的DEFLATE解压器都将
	// 继续能够解压此输出。
	HuffmanOnly = -2
)

const (
	logWindowSize = 15
	windowSize    = 1 << logWindowSize
	windowMask    = windowSize - 1

	// LZ77步骤产生一系列文字标记和<length，offset>
	// 成对标记。偏移量也称为距离。基础导线
	// 格式限制了长度和偏移的范围。例如，有
	// 256个合法长度：在[3258]范围内。此软件包的
	// 压缩器使用更高的最小匹配长度，支持优化
	// 例如通过32位加载和比较查找匹配。
	baseMatchLength = 3       // 根据RFC第3.2.5节的最小匹配长度
	minMatchLength  = 4       // 压缩器实际发出的最小匹配长度
	maxMatchLength  = 258     // 最大匹配长度
	baseMatchOffset = 1       // 最小匹配偏移量
	maxMatchOffset  = 1 << 15 // 最大匹配偏移量

	// 我们放入单个扁平块的最大令牌数，只是为了避免事情变得太大。
	maxFlateBlockTokens = 1 << 14
	maxStoreBlockSize   = 65535
	hashBits            = 17 // 17后性能下降
	hashSize            = 1 << hashBits
	hashMask            = (1 << hashBits) - 1
	maxHashOffset       = 1 << 24

	skipNever = math.MaxInt32
)

type compressionLevel struct {
	level, good, lazy, nice, chain, fastSkipHashing int
}

var levels = []compressionLevel{
	{0, 0, 0, 0, 0, 0}, // 无压缩。
	{1, 0, 0, 0, 0, 0}, // BestSpeed使用自定义算法；见deflatefast。去
	// 对于2-3级，我们不需要尝试惰性匹配。
	{2, 4, 0, 16, 8, 5},
	{3, 4, 0, 32, 32, 6},
	// 4-9级使用越来越多的懒惰匹配
	// 以及越来越严格的“足够好”条件。
	{4, 4, 4, 16, 16, skipNever},
	{5, 8, 16, 32, 32, skipNever},
	{6, 8, 16, 128, 128, skipNever},
	{7, 8, 32, 128, 256, skipNever},
	{8, 32, 128, 258, 1024, skipNever},
	{9, 32, 258, 258, 4096, skipNever},
}

type compressor struct {
	compressionLevel

	w          *huffmanBitWriter
	bulkHasher func([]byte, []uint32)

	// 压缩算法
	fill      func(*compressor, []byte) int // 将数据复制到窗口
	step      func(*compressor)             // 处理窗口
	sync      bool                          // 请求刷新
	bestSpeed *deflateFast                  // 编码器用于BestSpeed 

	// 输入哈希链
	// 如果哈希头[hashValue]在当前窗口
	// hashPrev[hashHead[hashValue]&windowMask]包含具有相同哈希值的上一个索引
	// 。
	chainHead  int
	hashHead   [hashSize]uint32
	hashPrev   [windowSize]uint32
	hashOffset int

	// 输入窗口：未处理的数据是窗口[index:windowEnd]
	index         int
	window        []byte
	windowEnd     int
	blockStart    int  // 当前令牌启动的窗口索引
	byteAvailable bool // 如果为真，仍需要处理窗口[index-1]。

	// 排队输出令牌
	tokens []token

	// 放气状态
	length         int
	offset         int
	hash           uint32
	maxInsertIndex int
	err            error

	// hashMatch必须能够包含最大匹配长度的哈希。
	hashMatch [maxMatchLength - 1]uint32
}

func (d *compressor) fillDeflate(b []byte) int {
	if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
		// 按窗口大小移动窗口
		copy(d.window, d.window[windowSize:2*windowSize])
		d.index -= windowSize
		d.windowEnd -= windowSize
		if d.blockStart >= windowSize {
			d.blockStart -= windowSize
		} else {
			d.blockStart = math.MaxInt32
		}
		d.hashOffset += windowSize
		if d.hashOffset > maxHashOffset {
			delta := d.hashOffset - 1
			d.hashOffset -= delta
			d.chainHead -= delta

			// 迭代切片而不是数组，以避免将整个表复制到堆栈上（问题#18625）。
			for i, v := range d.hashPrev[:] {
				if int(v) > delta {
					d.hashPrev[i] = uint32(int(v) - delta)
				} else {
					d.hashPrev[i] = 0
				}
			}
			for i, v := range d.hashHead[:] {
				if int(v) > delta {
					d.hashHead[i] = uint32(int(v) - delta)
				} else {
					d.hashHead[i] = 0
				}
			}
		}
	}
	n := copy(d.window[d.windowEnd:], b)
	d.windowEnd += n
	return n
}

func (d *compressor) writeBlock(tokens []token, index int) error {
	if index > 0 {
		var window []byte
		if d.blockStart <= index {
			window = d.window[d.blockStart:index]
		}
		d.blockStart = index
		d.w.writeBlock(tokens, false, window)
		return d.w.err
	}
	return nil
}

// fillWindow将使用提供的
// 字典填充当前窗口，并计算所有哈希值。
// 这比完全编码快得多。
// 只能在重置后使用。
func (d *compressor) fillWindow(b []byte) {
	// 如果我们处于仅限商店模式，请不要填充窗口。
	if d.compressionLevel.level < 2 {
		return
	}
	if d.index != 0 || d.windowEnd != 0 {
		panic("internal error: fillWindow called with stale data")
	}

	// 如果我们得到的太多，那就停止吧。
	if len(b) > windowSize {
		b = b[len(b)-windowSize:]
	}
	// 将所有内容添加到窗口。
	n := copy(d.window, b)

	// 一次计算256个哈希值（一级缓存命中次数更多）
	loops := (n + 256 - minMatchLength) / 256
	for j := 0; j < loops; j++ {
		index := j * 256
		end := index + 256 + minMatchLength - 1
		if end > n {
			end = n
		}
		toCheck := d.window[index:end]
		dstSize := len(toCheck) - minMatchLength + 1

		if dstSize <= 0 {
			continue
		}

		dst := d.hashMatch[:dstSize]
		d.bulkHasher(toCheck, dst)
		var newH uint32
		for i, val := range dst {
			di := i + index
			newH = val
			hh := &d.hashHead[newH&hashMask]
			// 使用相同的哈希值获取上一个值。
			// 我们的链应该指向前面的值。
			d.hashPrev[di&windowMask] = *hh
			// 将哈希链的头指向我们。
			*hh = uint32(di + d.hashOffset)
		}
		d.hash = newH
	}
	// 更新窗口信息。
	d.windowEnd = n
	d.index = n
}

// 尝试从长度大于prevSize的索引开始查找匹配项。
// 在放弃之前，我们只考虑链表计数的可能性。
func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
	minMatchLook := maxMatchLength
	if lookahead < minMatchLook {
		minMatchLook = lookahead
	}

	win := d.window[0 : pos+minMatchLook]

	// 当我们得到一个至少很长的匹配时，我们就退出了
	nice := len(win) - pos
	if d.nice < nice {
		nice = d.nice
	}

	// 如果我们有一个足够好的匹配，只看链中的1/4。
	tries := d.chain
	length = prevLength
	if length >= d.good {
		tries >>= 2
	}

	wEnd := win[pos+length]
	wPos := win[pos:]
	minIndex := pos - windowSize

	for i := prevHead; tries > 0; tries-- {
		if wEnd == win[i+length] {
			n := matchLen(win[i:], wPos, minMatchLook)

			if n > length && (n > minMatchLength || pos-i <= 4096) {
				length = n
				offset = pos - i
				ok = true
				if n >= nice {
					// 这场比赛已经足够好了，我们不想再找更好的了。
					break
				}
				wEnd = win[pos+n]
			}
		}
		if i == minIndex {
			// hashPrev[i&windowMask]已被覆盖，请立即停止。
			break
		}
		i = int(d.hashPrev[i&windowMask]) - d.hashOffset
		if i < minIndex || i < 0 {
			break
		}
	}
	return
}

func (d *compressor) writeStoredBlock(buf []byte) error {
	if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
		return d.w.err
	}
	d.w.writeBytes(buf)
	return d.w.err
}

const hashmul = 0x1e35a7bd

// hash4返回所提供切片的前4个字节的哈希表示形式
// 。
// 调用者必须确保len（b）>=4。
func hash4(b []byte) uint32 {
	return ((uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24) * hashmul) >> (32 - hashBits)
}

// bulkHash4将使用与hash4 
// matchLen返回a和b中匹配的字节数
func bulkHash4(b []byte, dst []uint32) {
	if len(b) < minMatchLength {
		return
	}
	hb := uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
	dst[0] = (hb * hashmul) >> (32 - hashBits)
	end := len(b) - minMatchLength + 1
	for i := 1; i < end; i++ {
		hb = (hb << 8) | uint32(b[i+3])
		dst[i] = (hb * hashmul) >> (32 - hashBits)
	}
}

// matchLen相同的算法计算哈希值
// 最大长度为'max'。两个片的大小必须至少为'max'
// 字节。
func matchLen(a, b []byte, max int) int {
	a = a[:max]
	b = b[:len(a)]
	for i, av := range a {
		if b[i] != av {
			return i
		}
	}
	return max
}

// encSpeed将压缩并存储当前添加的数据，
// 如果已经积累了足够的数据，或者我们在数据流的末尾。
// 发生的任何错误都将出现在d中。错误
func (d *compressor) encSpeed() {
	// 我们只有在使用maxStoreBlockSize时才进行压缩。
	if d.windowEnd < maxStoreBlockSize {
		if !d.sync {
			return
		}

		// 处理小尺寸。
		if d.windowEnd < 128 {
			switch {
			case d.windowEnd == 0:
				return
			case d.windowEnd <= 16:
				d.err = d.writeStoredBlock(d.window[:d.windowEnd])
			default:
				d.w.writeBlockHuff(false, d.window[:d.windowEnd])
				d.err = d.w.err
			}
			d.windowEnd = 0
			d.bestSpeed.reset()
			return
		}

	}
	// 对块进行编码。
	d.tokens = d.bestSpeed.encode(d.tokens[:0], d.window[:d.windowEnd])

	// 如果我们删除的数据少于1/16，哈夫曼将压缩块。
	if len(d.tokens) > d.windowEnd-(d.windowEnd>>4) {
		d.w.writeBlockHuff(false, d.window[:d.windowEnd])
	} else {
		d.w.writeBlockDynamic(d.tokens, false, d.window[:d.windowEnd])
	}
	d.err = d.w.err
	d.windowEnd = 0
}

func (d *compressor) initDeflate() {
	d.window = make([]byte, 2*windowSize)
	d.hashOffset = 1
	d.tokens = make([]token, 0, maxFlateBlockTokens+1)
	d.length = minMatchLength - 1
	d.offset = 0
	d.byteAvailable = false
	d.index = 0
	d.hash = 0
	d.chainHead = -1
	d.bulkHasher = bulkHash4
}

func (d *compressor) deflate() {
	if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
		return
	}

	d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
	if d.index < d.maxInsertIndex {
		d.hash = hash4(d.window[d.index : d.index+minMatchLength])
	}

Loop:
	for {
		if d.index > d.windowEnd {
			panic("index > windowEnd")
		}
		lookahead := d.windowEnd - d.index
		if lookahead < minMatchLength+maxMatchLength {
			if !d.sync {
				break Loop
			}
			if d.index > d.windowEnd {
				panic("index > windowEnd")
			}
			if lookahead == 0 {
				// 如果有，刷新电流输出块。
				if d.byteAvailable {
					// 仍有一个挂起的令牌需要刷新
					d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1])))
					d.byteAvailable = false
				}
				if len(d.tokens) > 0 {
					if d.err = d.writeBlock(d.tokens, d.index); d.err != nil {
						return
					}
					d.tokens = d.tokens[:0]
				}
				break Loop
			}
		}
		if d.index < d.maxInsertIndex {
			// 更新哈希
			d.hash = hash4(d.window[d.index : d.index+minMatchLength])
			hh := &d.hashHead[d.hash&hashMask]
			d.chainHead = int(*hh)
			d.hashPrev[d.index&windowMask] = uint32(d.chainHead)
			*hh = uint32(d.index + d.hashOffset)
		}
		prevLength := d.length
		prevOffset := d.offset
		d.length = minMatchLength - 1
		d.offset = 0
		minIndex := d.index - windowSize
		if minIndex < 0 {
			minIndex = 0
		}

		if d.chainHead-d.hashOffset >= minIndex &&
			(d.fastSkipHashing != skipNever && lookahead > minMatchLength-1 ||
				d.fastSkipHashing == skipNever && lookahead > prevLength && prevLength < d.lazy) {
			if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
				d.length = newLength
				d.offset = newOffset
			}
		}
		if d.fastSkipHashing != skipNever && d.length >= minMatchLength ||
			d.fastSkipHashing == skipNever && prevLength >= minMatchLength && d.length <= prevLength {
			// 上一步有一个匹配项，当前匹配项是
			// 不是更好。输出上一个匹配项。
			if d.fastSkipHashing != skipNever {
				d.tokens = append(d.tokens, matchToken(uint32(d.length-baseMatchLength), uint32(d.offset-baseMatchOffset)))
			} else {
				d.tokens = append(d.tokens, matchToken(uint32(prevLength-baseMatchLength), uint32(prevOffset-baseMatchOffset)))
			}
			// 在哈希表中插入所有字符串，直到匹配结束。
			// 已插入索引和索引-1。如果没有足够的
			// lookahead，则最后两个字符串不会插入哈希
			// 表。
			if d.length <= d.fastSkipHashing {
				var newIndex int
				if d.fastSkipHashing != skipNever {
					newIndex = d.index + d.length
				} else {
					newIndex = d.index + prevLength - 1
				}
				index := d.index
				for index++; index < newIndex; index++ {
					if index < d.maxInsertIndex {
						d.hash = hash4(d.window[index : index+minMatchLength])
						// 使用相同的哈希值获取上一个值。
						// 我们的链应该指向前面的值。
						hh := &d.hashHead[d.hash&hashMask]
						d.hashPrev[index&windowMask] = *hh
						// 将哈希链的头指向我们。
						*hh = uint32(index + d.hashOffset)
					}
				}
				d.index = index

				if d.fastSkipHashing == skipNever {
					d.byteAvailable = false
					d.length = minMatchLength - 1
				}
			} else {
				// 对于这么长的匹配，我们不需要将每个单独的
				// 项插入表中。
				d.index += d.length
				if d.index < d.maxInsertIndex {
					d.hash = hash4(d.window[d.index : d.index+minMatchLength])
				}
			}
			if len(d.tokens) == maxFlateBlockTokens {
				// 该块包含当前字符
				if d.err = d.writeBlock(d.tokens, d.index); d.err != nil {
					return
				}
				d.tokens = d.tokens[:0]
			}
		} else {
			if d.fastSkipHashing != skipNever || d.byteAvailable {
				i := d.index - 1
				if d.fastSkipHashing != skipNever {
					i = d.index
				}
				d.tokens = append(d.tokens, literalToken(uint32(d.window[i])))
				if len(d.tokens) == maxFlateBlockTokens {
					if d.err = d.writeBlock(d.tokens, i+1); d.err != nil {
						return
					}
					d.tokens = d.tokens[:0]
				}
			}
			d.index++
			if d.fastSkipHashing == skipNever {
				d.byteAvailable = true
			}
		}
	}
}

func (d *compressor) fillStore(b []byte) int {
	n := copy(d.window[d.windowEnd:], b)
	d.windowEnd += n
	return n
}

func (d *compressor) store() {
	if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
		d.err = d.writeStoredBlock(d.window[:d.windowEnd])
		d.windowEnd = 0
	}
}

// storeHuff压缩并存储当前添加的数据
// 当d.窗口已满或我们在流的末尾时。
// 发生的任何错误都将出现在d中。err 
func (d *compressor) storeHuff() {
	if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
		return
	}
	d.w.writeBlockHuff(false, d.window[:d.windowEnd])
	d.err = d.w.err
	d.windowEnd = 0
}

func (d *compressor) write(b []byte) (n int, err error) {
	if d.err != nil {
		return 0, d.err
	}
	n = len(b)
	for len(b) > 0 {
		d.step(d)
		b = b[d.fill(d, b):]
		if d.err != nil {
			return 0, d.err
		}
	}
	return n, nil
}

func (d *compressor) syncFlush() error {
	if d.err != nil {
		return d.err
	}
	d.sync = true
	d.step(d)
	if d.err == nil {
		d.w.writeStoredHeader(0, false)
		d.w.flush()
		d.err = d.w.err
	}
	d.sync = false
	return d.err
}

func (d *compressor) init(w io.Writer, level int) (err error) {
	d.w = newHuffmanBitWriter(w)

	switch {
	case level == NoCompression:
		d.window = make([]byte, maxStoreBlockSize)
		d.fill = (*compressor).fillStore
		d.step = (*compressor).store
	case level == HuffmanOnly:
		d.window = make([]byte, maxStoreBlockSize)
		d.fill = (*compressor).fillStore
		d.step = (*compressor).storeHuff
	case level == BestSpeed:
		d.compressionLevel = levels[level]
		d.window = make([]byte, maxStoreBlockSize)
		d.fill = (*compressor).fillStore
		d.step = (*compressor).encSpeed
		d.bestSpeed = newDeflateFast()
		d.tokens = make([]token, maxStoreBlockSize)
	case level == DefaultCompression:
		level = 6
		fallthrough
	case 2 <= level && level <= 9:
		d.compressionLevel = levels[level]
		d.initDeflate()
		d.fill = (*compressor).fillDeflate
		d.step = (*compressor).deflate
	default:
		return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
	}
	return nil
}

func (d *compressor) reset(w io.Writer) {
	d.w.reset(w)
	d.sync = false
	d.err = nil
	switch d.compressionLevel.level {
	case NoCompression:
		d.windowEnd = 0
	case BestSpeed:
		d.windowEnd = 0
		d.tokens = d.tokens[:0]
		d.bestSpeed.reset()
	default:
		d.chainHead = -1
		for i := range d.hashHead {
			d.hashHead[i] = 0
		}
		for i := range d.hashPrev {
			d.hashPrev[i] = 0
		}
		d.hashOffset = 1
		d.index, d.windowEnd = 0, 0
		d.blockStart, d.byteAvailable = 0, false
		d.tokens = d.tokens[:0]
		d.length = minMatchLength - 1
		d.offset = 0
		d.hash = 0
		d.maxInsertIndex = 0
	}
}

func (d *compressor) close() error {
	if d.err != nil {
		return d.err
	}
	d.sync = true
	d.step(d)
	if d.err != nil {
		return d.err
	}
	if d.w.writeStoredHeader(0, true); d.w.err != nil {
		return d.w.err
	}
	d.w.flush()
	return d.w.err
}

// NewWriter返回一个在给定级别压缩数据的新Writer。
// 在zlib之后，级别从1（最佳速度）到9（最佳压缩）；
// 较高级别通常运行较慢，但压缩更多。0级
// （无压缩）不尝试任何压缩；它只添加了
// 必要的放气框架。
// 级别-1（默认压缩）使用默认压缩级别。
// Level-2（HuffmanOnly）将仅使用哈夫曼压缩，使
// 对所有类型的输入进行非常快速的压缩，但牺牲了相当大的压缩效率。
// 
// 如果级别在范围[-2,9]内，则返回的错误将为零。
// 否则返回的错误将为非零。
func NewWriter(w io.Writer, level int) (*Writer, error) {
	var dw Writer
	if err := dw.d.init(w, level); err != nil {
		return nil, err
	}
	return &dw, nil
}

// NewWriterDict与NewWriter类似，但使用预设字典初始化新的
// Writer。返回的Writer的行为方式是
// 就好像字典是在没有生成任何压缩输出的情况下写入的一样。写入w 
// 的压缩数据只能由使用
// 同一字典初始化的读取器进行解压缩。
func NewWriterDict(w io.Writer, level int, dict []byte) (*Writer, error) {
	dw := &dictWriter{w}
	zw, err := NewWriter(dw, level)
	if err != nil {
		return nil, err
	}
	zw.d.fillWindow(dict)
	zw.dict = append(zw.dict, dict...) // 重置方法的重复字典。
	return zw, err
}

type dictWriter struct {
	w io.Writer
}

func (w *dictWriter) Write(b []byte) (n int, err error) {
	return w.w.Write(b)
}

// 写入程序获取写入其中的数据，并将压缩后的
// 格式的数据写入底层写入程序（请参见NewWriter）。
type Writer struct {
	d    compressor
	dict []byte
}

// Write将数据写入w，w最终会将压缩形式的数据写入其底层编写器。
func (w *Writer) Write(data []byte) (n int, err error) {
	return w.d.write(data)
}

// Flush将所有挂起的数据刷新到基础写入程序。
// 主要用于压缩网络协议，以确保远程读卡器有足够的数据来重建数据包。
// 在写入数据之前，Flush不会返回。
// 在没有挂起数据时调用Flush仍然会导致写入程序
// 发出至少4字节的同步标记。
// 如果基础写入程序返回错误，Flush将返回该错误。
// 
// 在zlib库的术语中，Flush相当于Z_SYNC_Flush。
func (w *Writer) Flush() error {
	// 有关刷新的详细信息：
	// https:
	return w.d.syncFlush()
}

// 关闭刷新并关闭写入程序。
func (w *Writer) Close() error {
	return w.d.close()
}

// 重置放弃写入程序的状态，使其等同于
// 使用dst 
// 和w的级别和字典调用NewWriter或NewWriterDict的结果。
func (w *Writer) Reset(dst io.Writer) {
	if dw, ok := w.d.w.writer.(*dictWriter); ok {
		// w是用NewWriter创建的ICT 
		dw.w = dst
		w.d.reset(dw)
		w.d.fillWindow(w.dict)
	} else {
		// w是用NewWriter 
		w.d.reset(dst)
	}
}
